iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0

今日題目

題目連結:144. Binary Tree Preorder Traversal
題目主題:Stack, Tree, Depth-First Search, Binary Tree

前一篇提到了Heap是一個Tree的結構,這次開始正式進入Tree的世界。今天要分享如何想像 Tree 的樣子,學習如何讀這顆樹的資料。而接下來的三個題目我們是用 Depth-First Search 深度優先的方式來解題。


簡單說說 Tree

接下來會有很多題目會看到像下圖這樣的註解:
https://ithelp.ithome.com.tw/upload/images/20210924/201413368nYTn5WVeg.png

這是在說明一個樹的節點長什麼樣子,稱它TreeNode,每個節點會有三個屬性。

  1. val:這個節點的值。
  2. left:是一個TreeNode,這個節點的子層左節點。
  3. right:是一個TreeNode,這個節點的子層右節點。

以下是一個範例,可以這樣想像:
https://ithelp.ithome.com.tw/upload/images/20210924/20141336NSsxx4gmjo.png

上圖中,黑色的方框是一個TreeNode,可以看到他實際的val是5,左邊紅色方框是 left 子層左節點(TreeNode),右邊綠色方框是 right 子層右節點(TreeNode)。再以紅色方框的TreeNode為例,這是一個沒有子層右節點的TreeNode,這樣的狀況是有可能的。當然這只是一個範例,實際上一棵樹可能長的更大,最下層的 2 這個子節點下面可能還有一個left節點跟right節點這樣長下去。

另外要提的是,接下來給的題目,都會給這樣的範例,如下圖:
https://ithelp.ithome.com.tw/upload/images/20210924/2014133617Yxecqqxi.png
所以在這邊也要先分享,如何將一個陣列看成一棵樹?拿昨天的範例當例子。

https://ithelp.ithome.com.tw/upload/images/20210924/20141336RxD5rdv9E6.png

實際上這棵樹轉成陣列以後,會長這個樣子:
tree = [1, 4, 6, 14, 13, 11, 16]
那如果沒有這個圖,只有陣列時,應該要怎麼看呢?

https://ithelp.ithome.com.tw/upload/images/20210924/20141336IBtuwaibGq.png

如上圖,每一層有多少數量就是用 2 的次方來看。
第一層是 2 的 0 次方,只有一個,而這個就是樹的根節點。
第二層是 2 的 1 次方是2,所以有兩個元素,分別是根節點的子層左節點及子層右節點。
第三層是 2 的 2 次方總共有四個,從左邊排到右邊,14、13 就是 4 的子節點,11、16就是6的子節點。
假設這棵樹繼續長第四層,就會是 2 的 3 次方,總共會有8個節點,依此類推。
最後再看一次對應圖。

https://ithelp.ithome.com.tw/upload/images/20210924/20141336qEZYx1eoUx.png


簡單說說 Preorder Traversal

在DFS(Depth-First Search)中Traversal分成三種方式:

  1. Preorder
  2. Inorder
  3. Postorder

今天會用到的就是Preorder Traversal。
Preorder的原則就是,進入一個節點時,馬上讀取它的值,假設資料是 tree = [5, 2, 6, 1, 3, null, 8]

https://ithelp.ithome.com.tw/upload/images/20210924/20141336D8yZj9aU8V.png

上圖中,每個節點上面的數字是讀的順序,而紅色虛線箭頭就是讀的方向。
Preorder排出來就會是 [5, 2, 1, 3, 6, 8]。


題目解說

建議可以看看LeetCode原本的題目說明,這邊是用我的方式說明題目,參考就好。

今天的題目,目標就是用Preorder的方式來讀取樹,依照Preorder的順序將節點的值排到一個列表中,最後回傳這個列表。

約束:

  • 樹的節點總數範圍在 [0, 100]
  • 100 <= Node.val <= 100

範例1

輸入: root = [1,null,2,3]
輸出: [1,2,3]

範例2

輸入: root = []
輸出: []

範例3

輸入: root = [1]
輸出: [1]

範例4

輸入: root = [1,2]
輸出: [1,2]

範例5

輸入: root = [1, null, 2]
輸出: [1,2]

建議到這邊先停下來,嘗試自己解解看,若沒有想法可再繼續走下去。


解題的想像

文字描述

  1. 寫一個遞迴方法,這個方法要能傳入前往的節點及要完成的list。
  2. 每呼叫一次這個方法會往一個節點前進,
  3. 這個遞迴會一直到走到發現沒有節點才會往回走。
  4. 每進入一個節點的當下會將目前節點的值紀錄到list中。
  5. 最終跑完所有節點會回傳一份用Preorder排出來的list。

圖解過程

範例:tree = [5, 2, 6, null, 8]

下圖中是實際上Traversal在走的過程,實際在想像移動過程的時候,建議在最下面的節點都補虛線的節點代表走到底了。

https://ithelp.ithome.com.tw/upload/images/20210924/20141336KX0XcqxFhy.png

  1. step1 及 step2都直接進入了一個新節點,紅色圓就是目前要紀錄到list的數字。
  2. step3 及 step4實際走到一個紅色圓,都有一個路徑,這個路徑是實際上走到紅色圓之前會先經過的節點。
  3. step5 會把剩下的虛線節點走完,確認整棵樹走過一次,再走回根節點結束這個Traversal。
  4. 走完step1 ~ step5以後,就會組成step6看到的list,這個list是過程中出現的紅色圓一個一個組成的,也就是Preorder Traversal最後要回傳的結果。

若因為沒想法而走到這邊,建議看完想像以後再給自己一次機會試一次。


程式碼撰寫

class Solution:
    # root 要進入的節點
    # preorder_list 最終要回傳的list
    def traversal(self, root: TreeNode, preorder_list: List[int]):
        # 沒有節點往回走
        if root == None: return preorder_list
        # 進入節點紀錄目前的值
        preorder_list.append(root.val)
        # 前往左邊子節點
        preorder_list = self.traversal(root.left, preorder_list)
        # 前往右邊子節點
        preorder_list = self.traversal(root.right, preorder_list)
        return preorder_list
    
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])

希望您今天能瞭解到...

  1. TreeNode的長相
  2. 將陣列看成一個樹的結構
  3. Preorder Traversal
  4. 144. Binary Tree Preorder Traversal的解題方法

若內容有什麼問題或建議歡迎一起交流:)
感謝您今天願意花時間看完這篇文章~~~~

Next:94. Binary Tree Inorder Traversal


上一篇
Day 9:1046. Last Stone Weight
下一篇
Day 11:94. Binary Tree Inorder Traversal
系列文
我在刷LeetCode時邂逅了Python30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言